Sequences whose characteristics are known to a receiver are used for a number of purposes in digital communication systems. For example, different portions of a long sequence can be assigned as characteristic addresses to a number of individual receivers in a group. In a secure transmission system, synchronized pseudo-random sequences can be used in a transmitter to encrypt messages and in a receiver to recover them. These and other applications require that the receiver be able to detect sequences in the presence of arbitrary digital data.
Linear feedback shift register (LFSR) sequences have frequently been used for these purposes. An LFSR sequence has the property that, by knowing a small portion of it and the rules for deriving it, a receiver can compute the entire sequence. Making use of this property, one method to detect an LFSR sequence within a received bit stream is to have in both transmitter and receiver shift registers that generate sequences according to the same algorithm. The receiver loads a portion of the bit stream into its local shift register and then sequences through successive states in time with the received bit stream. A detector correlates the local sequence with the incoming bit stream. If sufficient bits agree within a given measuring interval, then the detector concludes that the incoming bits do comprise the LFSR sequence and provides a detection indication. If too many bits disagree, the receiver can repeat the search for the sequence by reloading its shift register from incoming bits, generating a new sequence, and again comparing. The receiver can repeat the search until it detects the sequence or terminates the search for some other reason.
To locate a sequence by the method described above requires that the local sequence be correctly generated. This, in turn, requires that the entire portion of the bit stream from which the local shift register begins its sequence be loaded without errors. Errors introduced during transmission over a noisy channel can corrupt the bit stream and reduce the probability of correctly loading the register. To overcome the effects of noise and increase the probability of locating the sequence, a receiver can use digital error correction.
Some error correction methods add redundancy to the transmitted message by including parity bits, which provide the information needed by the receiver to make correct decisions from corrupted data. This redundancy is inherent in an LFSR sequence, since each calculated parity bit feeds back as the next information bit.
Correcting errors in an LFSR sequence is described in U.S. Pat. No. 4,667,327, entitled "Error Corrector for a Linear Feedback Shift Register Sequence," issued May 19, 1987, to Bright et al., which is assigned to the same assignee as the present invention, and is incorporated by reference as if set forth fully herein. In the method described in that patent, the error corrector shifts bits into a register as they are received and generates parity bits according to the characteristic polynomial used in the transmitter for generating the LFSR sequence. It does not feed back the parity bits; instead, it compares subsequently received bits with corresponding parity bits and stores the comparison results in a syndrome register. It computes estimates of the errors from the contents of the syndrome register and uses the estimates to correct errors in the received sequence.
For detection in a noisy transmission environment, it would appear desirable to combine error correction with the method described earlier for detection of an LFSR sequence. It has been found, however, that this combination has the undesirable property that, when the input to the detector is random data or noise, the detector has a high probability of erroneously indicating the presence of an LFSR sequence. This results because the error correction process creates short-term correlation between the locally generated sequence and the random input signal from which it was derived. The sequence generated from the vector of error-corrected, random input bits will correlate with the random input over a certain number of bits before or after the vector.
Without this short-term correlation, comparisons between successive bits of the local sequence and a random input sequence would agree only about fifty percent of the time. Because of the correlation, comparisons agree significantly more often than fifty percent of the time. The number of agreements can be sufficiently large to satisfy the criterion for indicating detection of an LFSR sequence. Such an indication is known as a "false" detection.
The problem thus facing those skilled in the art is that the sequence detection method requires error correction to function properly under certain conditions, such as when noise corrupts the transmitted data, but error correction as known in the prior art may result in an intolerable rate of false detection when only random data or noise is being received.